package problem;

public class S_134 {
    //加油站
    //1.暴力
    class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int n = gas.length;
            for (int i = 0; i < n; i++) {
                int remain = gas[i];
                int j = i;
                while (remain - cost[j] >= 0) {
                    remain = remain - cost[j] + gas[(j + 1) % n];
                    j = (j + 1) % n;
                    if (j == i) return i;
                }
            }
            return -1;
        }
    }

    //2.优化
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        //记录能到的最远距离
        int[] farIndex = new int[n];
        for (int i = 0; i < farIndex.length; i++) {
            farIndex[i] = -1;
        }
        //记录到达最远距离时候剩余的汽油
        int[] farIndexRemain = new int[n];
        for (int i = 0; i < n; i++) {
            int j = i;
            int remain = gas[i];
            while (remain - cost[j] >= 0) {
                //到达下个点后的剩余
                remain = remain - cost[j];
                j = (j + 1) % n;
                //判断之前有没有考虑过这个点
                if (farIndex[j] != -1) {
                    //加上当时剩余的汽油
                    remain = remain + farIndexRemain[j];
                    //j 进行跳跃
                    j = farIndex[j];
                } else {
                    //加上当前点的补给
                    remain = remain + gas[j];
                }
                if (j == i) {
                    return i;
                }
            }
            //记录当前点最远到达哪里
            farIndex[i] = j;
            //记录当前点的剩余
            farIndexRemain[i] = remain;
        }
        return -1;
    }

    //总
    class Solution1 {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int total = 0, sum = 0, start = 0;
            for (int i = 0; i < gas.length; ++i) {
                total += gas[i] - cost[i];
                sum += gas[i] - cost[i];
                if (sum < 0) {
                    start = i + 1;
                    sum = 0;
                }
            }
            return (total < 0) ? -1 : start; // total 小于 0，说明总消耗大于总油量，那必定无法行驶完所有站点
        }
    }
}

